/*
 * Hash.cpp
 *
 *  Created on: 01/11/2011
 *      Author: damnvb
 */

#include "Hash.h"
#include "Bucket.h"
#include "Util.h"
#include <vector>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <stdlib.h>

int Hash::REG_NO_EN_HASH = -1;
int Hash::RES_OK = -3;

Hash::Hash(string pathBloques, string pathBloquesLibres, string pathTabla) {
	this->pathBloques = pathBloques;
	this->pathBloquesLibres = pathBloquesLibres;
	this->pathTabla = pathTabla;

	this->archBloques = new fstream();
	this->archBloquesLibres = new fstream();
	this->archTabla = new fstream();

	//escribe el tamaño y la primera dirección de la tabla de dispersión
	unsigned int tamanioTabla = 1;
	archTabla->open(this->pathTabla.c_str(), ios::in | ios::binary);

	if (!archTabla->is_open()) {
		archTabla->open(this->pathTabla.c_str(), ios::out |ios::binary);
		archTabla->seekp(0, ios_base::beg);
		archTabla->write(Util::IntToString(tamanioTabla).c_str(), sizeof(unsigned int));

		unsigned int direccion = 0;
		archTabla->write(Util::IntToString(direccion).c_str(), sizeof(unsigned int));
	}
	archTabla->close();

	//escribe el primer bloque en el hash
//	unsigned int tam = tamanioTabla;//obtenerTamanioTabla();	// LECTURA AL PEDO??
	Bucket *primer_bloque = new Bucket(this->pathBloques.c_str(),0);
	primer_bloque->persistir(this->pathBloques.c_str(), 0);
	delete primer_bloque;

	numeritoMagico = 0;
}

unsigned int Hash::obtenerTamanioTabla(){

	archTabla->open(this->pathTabla.c_str(), ios::binary | ios::in);
	archTabla->seekg(0, ios_base::beg);
	string aux;
	aux.resize(sizeof(unsigned int));
	archTabla->read(&(aux[0]), sizeof(unsigned int));
	archTabla->close();
	return Util::stringToInt(aux);
}

unsigned long Hash::funcionHashing(Registro *unRegistro){

	unsigned int suma = 0, i = 0;
//	char caracter = unRegistro->getKey()[0];
//	while (caracter != '\0'){
//		suma += caracter + '0';
//		i++;
//		caracter = unRegistro->getKey()[i];
//	}
	string key = unRegistro->getKey();
	for (unsigned int i = 0; i < key.length(); i++)
		suma += (unsigned int)key[i];

	vector<unsigned int> tabla_en_memoria = cargarTablaDispersion();
//	cout << "El registro " << unRegistro->getKey() << " va a parar a " << (tabla_en_memoria)[suma%obtenerTamanioTabla()+1 ] << endl;
	return (suma%obtenerTamanioTabla())+1;
	/* suma uno para no tener en cuenta la primera posición de la tabla,
	 * donde se guarda la longitud de la misma */
}

void Hash::persistirVector(vector<unsigned int> vec, fstream *archivo, const char* nombre_archivo){
		archivo->open(nombre_archivo, ios::binary | ios::out);
		archivo->seekp(0, ios_base::beg);
		for(unsigned int i = 0; i <= (vec)[0]; i++)
			archivo->write(Util::IntToString(vec[i]).c_str(), sizeof(unsigned int));
		archivo->close();
}

unsigned int Hash::extraerNroNuevoBloque(){
	//- toma el menor numero de bloque del archivo de bloques libres y lo elimina del archivo
	//- si no hay bloques libres, devuelve el número de bloque en uso más alto + 1
	unsigned int num_bloque;
	unsigned int posicion_num_bloque;
	vector<unsigned int> lista_bloques = cargarArchivoBloquesLibres();

	if ((lista_bloques)[0] != 0){
		num_bloque = (lista_bloques)[1];
		posicion_num_bloque = 1;
		for(unsigned int i = 2; i < lista_bloques.size(); i++){
			if ((lista_bloques)[i] < num_bloque){
				num_bloque = (lista_bloques)[i];
				posicion_num_bloque = i;
			}
		}
		(lista_bloques)[posicion_num_bloque] = lista_bloques.back();
		lista_bloques.pop_back();
		persistirVector(lista_bloques, archBloquesLibres, this->pathBloquesLibres.c_str());
//		delete lista_bloques;
		return num_bloque;
	}
//	delete lista_bloques;

	vector<unsigned int> tablaDisp = cargarTablaDispersion();
	int max = -1;
	for(unsigned int i = 1; i <= tablaDisp[0]; i++)
		if((int)(tablaDisp[i]) > max) max = tablaDisp[i];  // TODO CHECK THIS

	return max + 1;
}

vector<unsigned int> Hash::cargarArchivoBloquesLibres(){

	archBloquesLibres->open(this->pathBloquesLibres.c_str(), ios::binary | ios::in);
	archBloquesLibres->seekg(0, ios_base::beg);
	vector<unsigned int> tabla_en_memoria;
	string datos;
	datos.resize(sizeof(unsigned int));
	archBloquesLibres->read(&(datos[0]), sizeof(unsigned int));

	tabla_en_memoria.push_back(Util::stringToInt(datos));

	for(unsigned int i = 1; i <= tabla_en_memoria[0]; i++){
		archBloquesLibres->read(&(datos[0]), sizeof(unsigned int));
		tabla_en_memoria.push_back(Util::stringToInt(datos));
	}

	archBloquesLibres->close();
	return tabla_en_memoria;
}

vector<unsigned int> Hash::cargarTablaDispersion(){

	archTabla->open(this->pathTabla.c_str(), ios::binary | ios::in);
	archTabla->seekg(0, ios_base::beg);
	vector<unsigned int> tabla_en_memoria;
	string datos;
	datos.resize(sizeof(unsigned int));
	archTabla->read(&(datos[0]), sizeof(unsigned int));

	tabla_en_memoria.push_back(Util::stringToInt(datos));

	for(unsigned int i = 1; i <= tabla_en_memoria[0]; i++){
		archTabla->read(&(datos[0]), sizeof(unsigned int));
		tabla_en_memoria.push_back(Util::stringToInt(datos));
	}

	archTabla->close();
	return tabla_en_memoria;
}

int Hash::buscar(Registro *unRegistro){
	//obtiene la posicion del bloque donde está el registro
	vector<unsigned int> tabla_en_memoria = cargarTablaDispersion();
	long offset_bloque = tabla_en_memoria[funcionHashing(unRegistro)];

	//lee el bloque a memoria para buscar el registro.
	//Si no está lanza excepción, si está lo devuelve por parámetro
	Bucket *bloque_aux = new Bucket(this->pathBloques.c_str(), offset_bloque);

	if (bloque_aux->buscar(unRegistro) == Bucket::REG_NO_EN_BUCKET) {
		delete bloque_aux;
		return REG_NO_EN_HASH;
	}
	else{
		delete bloque_aux;
		return RES_OK;
	}
}

void Hash::duplicarTabla(unsigned int posicion_en_tabla){

	vector<unsigned int> tabla_en_memoria = cargarTablaDispersion();

	cout << "Tamaño Tabla Antes de Duplicar: " << tabla_en_memoria.size() << endl << endl;

	unsigned int tamanio_tabla = (tabla_en_memoria)[0];
	tabla_en_memoria.reserve(tamanio_tabla*2 + 1);

	//duplica la tabla en memoria
	for(unsigned int i = 1; i <= tamanio_tabla; i++)
		tabla_en_memoria.push_back(tabla_en_memoria[i]);

	cout << "Tamaño Tabla Despues de Duplicar: " << tabla_en_memoria.size() << endl << endl;

	//lee el nro. de bloque desbordado, y en la primera mitad de la
	//tabla lo reemplaza por el nuevo número de bloque
	unsigned int nro_bloque_desbordado = (tabla_en_memoria)[posicion_en_tabla];
	unsigned int num_nuevo_bloque = extraerNroNuevoBloque();
	(tabla_en_memoria)[posicion_en_tabla] = num_nuevo_bloque;

	//duplica el tamaño de la tabla y guarda la tabla duplicada en disco
	(tabla_en_memoria)[0] *= 2;
	persistirVector(tabla_en_memoria, archTabla, this->pathTabla.c_str());

	//en el archivo de bloques inserta uno nuevo, y al nuevo bloque y al
	//desbordado les asigna tamanio dispersion = tamanio tabla
	Bucket *nuevo_bloque = new Bucket(obtenerTamanioTabla());
	nuevo_bloque->persistir(this->pathBloques.c_str(), num_nuevo_bloque);
	delete nuevo_bloque;

	long offset_bloque = nro_bloque_desbordado;
	Bucket *bloque_desbordado = new Bucket(this->pathBloques.c_str(), offset_bloque);
	bloque_desbordado->setTamanioDispersion(obtenerTamanioTabla());
	// Borra todos los registros del bloque y los guarda en memoria
	vector<Registro*> registros_a_redispersar = bloque_desbordado->vaciar();

	//vuelve a guardar el bloque, ahora sin registros y con su nuevo tamaño de dispersión:
	bloque_desbordado->persistir(this->pathBloques.c_str(), offset_bloque);
	delete bloque_desbordado;
	//redispersa los registros del bloque desbordado

	for(unsigned int i = 0; i < registros_a_redispersar.size(); i++)
		this->guardar(registros_a_redispersar[i]);
	for(unsigned int i = 0; i < registros_a_redispersar.size(); i++)
		delete registros_a_redispersar[i];
}


void Hash::incrementarTabla(unsigned int posicion_en_tabla){
	//lee y duplica el tamaño de dispersión del bloque desbordado

	vector<unsigned int> tabla_disp = cargarTablaDispersion();
	long offset_bloque = tabla_disp[posicion_en_tabla];

	Bucket *bloque_desbordado = new Bucket(this->pathBloques.c_str(), offset_bloque);
	unsigned int nuevo_tamanio_dispersion = bloque_desbordado->getTamanioDispersion()*2;
	bloque_desbordado->setTamanioDispersion(nuevo_tamanio_dispersion);

	//Borra todos los registros del bloque y los guarda en memoria

	vector<Registro*> registros_a_redispersar = bloque_desbordado->vaciar();
	//vuelve a guardar el bloque, ahora sin registros y con su nuevo tamaño de dispersión:
	bloque_desbordado->persistir(this->pathBloques.c_str(), offset_bloque);
	delete bloque_desbordado;

	//inserta un nuevo bloque con el nuevo tamaño de dispersión
	Bucket *nuevo_bloque = new Bucket(nuevo_tamanio_dispersion);
	unsigned int num_nuevo_bloque = extraerNroNuevoBloque();
	nuevo_bloque->persistir(this->pathBloques.c_str(), num_nuevo_bloque);
	delete nuevo_bloque;

	//y asigna su referencia a todas las posiciones de la tabla
	//que estén a distancia n*nuevo_tamanio_dispersion

	unsigned int posicion = posicion_en_tabla;
	unsigned int distancia = 0;
	unsigned int tamanio_tabla = tabla_disp[0];
	do{
		if(distancia%nuevo_tamanio_dispersion == 0) tabla_disp[posicion] = num_nuevo_bloque;

		if(posicion + 1 > tamanio_tabla) posicion = 1;
		else posicion++;
		distancia++;
	}while(posicion != (posicion_en_tabla));
	persistirVector(tabla_disp, archTabla, this->pathTabla.c_str());

	//redispersa los registros del bloque desbordado

	for(unsigned int i = 0; i < registros_a_redispersar.size(); i++)
		this->guardar(registros_a_redispersar[i]);
	for(unsigned int i = 0; i < registros_a_redispersar.size(); i++)
		delete registros_a_redispersar[i];
}


void Hash::expandirHash(unsigned int posicion_en_tabla){

	numeritoMagico = 1;
	vector<unsigned int> tabla_disp = this->cargarTablaDispersion();
	long offset_bloque = tabla_disp[posicion_en_tabla];
	Bucket *bloque_aux = new Bucket(this->pathBloques.c_str(), offset_bloque);
	unsigned int tamanio_dispersion = bloque_aux->getTamanioDispersion();
	delete bloque_aux;
	unsigned int tamanio_tabla = obtenerTamanioTabla();

	if (tamanio_dispersion == tamanio_tabla) duplicarTabla(posicion_en_tabla);
	else if (tamanio_dispersion < tamanio_tabla) incrementarTabla(posicion_en_tabla);
}


void Hash::guardar(Registro *elRegistro){

	vector<unsigned int> tabla_disp = this->cargarTablaDispersion();
	long offset_bloque = tabla_disp[funcionHashing(elRegistro)];
	Registro *unRegistro = new Registro(elRegistro->getKey());
	Bucket *bloque_aux = new Bucket(this->pathBloques.c_str(), offset_bloque);

	/* busca el registro en el bloque. Si no está lo inserta y sale */
//	Registro *registro_anterior;

	if(bloque_aux->buscar(unRegistro) == Bucket::REG_NO_EN_BUCKET)
	{
		int result = bloque_aux->insertar(elRegistro);
		if(result == Bucket::RES_OK){
			bloque_aux->persistir(this->pathBloques.c_str(), offset_bloque);
			delete bloque_aux;
			delete unRegistro;
			return;
		} else {
			if (result == Bucket::REG_MAYOR_QUE_BUCKET) {
				bloque_aux->persistir(this->pathBloques.c_str(), offset_bloque);
				delete bloque_aux;
				delete unRegistro;
				return;
			}
			/* si el bloque estaba lleno y no se pudo insertar el registro,
			 * agrega otro bloque, modifica la tabla, redispersa, guarda y termina */
			delete bloque_aux;
			if (numeritoMagico == 0){
				expandirHash(funcionHashing(elRegistro));
				guardar(elRegistro);
			}
			delete unRegistro;
			return;
		}
	}else {
		 /* Si ya estaba fusiona las listas de referencias y luego inserta */
		 /* HACER: en la sobrecarga del operador + validar
		  * longitud (si la lista creció demasiado, guarda en archivo de listas) */


		 Registro *nuevo_registro =  (*elRegistro) + (*unRegistro);
		 delete unRegistro;
		 /* NOTA: bloque::insertar(registro) está implementado de forma tal que si
		  * el registro ya estaba en el bloque, el viejo es reemplazado por el nuevo */

		 int result = bloque_aux->insertar(nuevo_registro);
		 if(result == Bucket::RES_OK){
			 bloque_aux->persistir(this->pathBloques.c_str(), offset_bloque);
			 delete bloque_aux;
			 delete nuevo_registro;
			 return;
		 } else {
			 if (result == Bucket::REG_MAYOR_QUE_BUCKET) {
				bloque_aux->persistir(this->pathBloques.c_str(), offset_bloque);
				delete bloque_aux;
				delete nuevo_registro;
				return;
			 }
			 /* si el bloque estaba lleno y no se pudo insertar el registro,
			 * agrega otro bloque, modifica la tabla, redispersa, guarda y termina */
			 delete bloque_aux;
			 expandirHash(funcionHashing(nuevo_registro));
			 guardar(nuevo_registro);
			 delete nuevo_registro;
			 return;
		 }
	}
}

void Hash::borrar(Registro *unRegistro){

	vector<unsigned int> tabla = cargarTablaDispersion();
	long offset_bloque = (tabla)[funcionHashing(unRegistro)];
	Bucket *bloque_aux = new Bucket(this->pathBloques.c_str(), offset_bloque);

	bloque_aux->borrar(unRegistro);
	bloque_aux->persistir(this->pathBloques.c_str(), offset_bloque);

	/* revisa si el bloque quedó vacío para tratar de liberarlo*/
	if(bloque_aux->getCantidadRegistros() == 0)
		reducirHash(funcionHashing(unRegistro));
	delete bloque_aux;
}


void Hash::reducirHash(unsigned int posicion_en_tabla){

	vector<unsigned int> tabla = cargarTablaDispersion();
	unsigned int tamanio_tabla = (tabla)[0];
	unsigned int nro_bloque_vacio = (tabla)[posicion_en_tabla];

	/* calcula la distancia que hay que moverse a derecha e izquierda de
	 * posicion_en_tabla para ver si los números de bloque consignados en esas
	 * posiciones coinciden y determinar si el bloque puede o no ser liberado*/
	long offset_bloque = (tabla)[posicion_en_tabla];
	Bucket *bloque_vacio = new Bucket(this->pathBloques.c_str(), offset_bloque);

	unsigned int distancia_final = bloque_vacio->getTamanioDispersion()/2;
	unsigned int posicion_adelante = posicion_en_tabla;
	unsigned int posicion_atras = posicion_en_tabla;
	unsigned int distancia_actual = 0;

	delete bloque_vacio;

	do{
		if(posicion_adelante + 1 > tamanio_tabla) posicion_adelante = 1;
		else posicion_adelante++;
		distancia_actual++;
	}while(distancia_actual < distancia_final);

	distancia_actual = 0;
	do{
		if(posicion_atras - 1 < 1) posicion_atras = tamanio_tabla;
		else posicion_atras--;
		distancia_actual++;
	}while(distancia_actual < distancia_final);

	/* si coinciden recorre la tabla de dispersión y en cada posición a distancia
	 * n*distancia_final del bloque vacío asigna el número de bloque que lo reemplaza */
	if((tabla)[posicion_atras] == (tabla)[posicion_adelante]){
		unsigned int bloque_a_asignar = (tabla)[posicion_atras];
		unsigned int distancia = 0;
		unsigned int posicion = posicion_en_tabla;
		do{
			if(distancia%distancia_final == 0) (tabla)[posicion] = bloque_a_asignar;

			if(posicion + 1 > tamanio_tabla) posicion = 1;
			else posicion++;
			distancia++;
		}while(posicion != posicion_en_tabla);

		persistirVector(tabla, archTabla, this->pathTabla.c_str());

		//libera el bloque vacío (agrega al archivo de bloques libres)
		vector<unsigned int> lista_bloques_libres = cargarArchivoBloquesLibres();
		((lista_bloques_libres)[0])++;
		lista_bloques_libres.reserve((lista_bloques_libres)[0] + 1);
		(lista_bloques_libres)[(lista_bloques_libres)[0]] = nro_bloque_vacio;
		persistirVector(lista_bloques_libres, archBloquesLibres, this->pathBloquesLibres.c_str());

		//al bloque reemplazante le divide por 2 el tamaño de dispersion
		long offset_reemplazante = posicion_en_tabla;
		Bucket *bloque_reemplazante = new Bucket(this->pathBloques.c_str(), offset_reemplazante);
		unsigned int nuevo_tam_dispersion = bloque_reemplazante->getTamanioDispersion()/2;
		bloque_reemplazante->setTamanioDispersion(nuevo_tam_dispersion);
		bloque_reemplazante->persistir(this->pathBloques.c_str(), offset_reemplazante);
		delete bloque_reemplazante;

		//si las dos mitades son iguales trunca la tabla
		bool distintas = false;
		for(unsigned int i = 1; i <= tamanio_tabla/2; i++){
			if((tabla)[i + tamanio_tabla] != (tabla)[i])
				distintas = true;
		}
		if (!distintas){
			vector<unsigned int> aux;
			aux.reserve(tamanio_tabla/2 +1);
			(aux)[0] = tamanio_tabla/2;
			for(unsigned int i = 1; i <= tamanio_tabla/2; i++)
				(aux)[i] = (tabla)[i];

			persistirVector(aux, archTabla, this->pathTabla.c_str());
		}
	}
}




Hash::~Hash() {
	delete this->archBloques;
	delete this->archBloquesLibres;
	delete this->archTabla;
}

